public class code3 {
//    力扣 150 合并两个有序链表

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 思路一：这道题目可以使用双指针进行合并

        // 首先定义一个新的头结点，作为最终返回值的头
        ListNode newHead = new ListNode(-1);

        // 针对这个节点创建出一个指针
        ListNode flag  = newHead;

        // 让两个链表进行循环比较，这里比较的肯定是相同长度下的值
        while(list1 != null && list2 != null) {
            // 此时尝试让两个节点的值进行比较
            if(list1.val <= list2.val) {
                flag.next = list1;
                // 让指针进行后移
                list1 = list1.next;
            } else {
                flag.next = list2;
                list2 = list2.next;
            }
            // 还需要让 flag 指针向后进行移动
            flag = flag.next;
        }
        // 当相同长度判断结束后，还需要将更长的一部分截取下来添加到这个链表的尾巴后面
        if(list1 == null) {
            flag.next = list2;
        }
        if(list2 == null) {
            flag.next = list1;
        }

        // 最终返回这个新的头结点
        return newHead.next;
    }
}
